package leetcode_day._2021._202108._1120;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/8/12 19:33
 * 最长回文子序列
 * 算法：动态规划
 * 从右下往上遍历 dp 数组
 * 判断 i 到 j 是否是回文串，要看 i + 1 到 j - 1 之间是否是回文串
 */
public class _12_516 {
    public static void main(String[] args) {
        System.out.println(new _12_516().longestPalindromeSubseq("bbbab"));
    }

    public int longestPalindromeSubseq(String s) {
        char[] array = s.toCharArray();
        int len = array.length;
        int[][] dp = new int[len][len];
        for (int i = len - 1; i >= 0; i--) {
            for (int j = i; j < len; j++) {
                if (i == j) dp[i][j] = 1;
                else {
                    if (array[i] == array[j]) dp[i][j] = dp[i + 1][j - 1] + 2;
                    else dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]);
                }
            }
        }
        return dp[0][len - 1];
    }

}
